package arraytraversal;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author Seabook
 *
 */
public class ArrayTraversal2 {
	int x = 0;
	int y = 0;

	public static void main(String[] args) {

		ArrayTraversal2 at = new ArrayTraversal2();
		int[] org = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
		int[][] matrix = at.convert2Matrix(org);
		at.print(matrix);

		Integer[] traversedArray = at.traverseArray(matrix, org);

		for (int i : traversedArray) {
			System.out.print(i + ", ");
		}
		System.out.println();
	}

	private int[][] convert2Matrix(int[] is) {
		int length = is.length;
		int n = (int) Math.sqrt(length);


		int[][] matrix = new int[n][n];

		int i = 0;
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				matrix[j][k] = is[i];
				i++;
			}
		}
		return matrix;
	}


	public Integer[] traverseArray(int[][] matrix, int[] org) {
		List<Integer> traverseArray = new ArrayList<Integer>();
		traverseArray.add(matrix[x][y]);

		for (int i = 0; i < org.length - 1; i++) {

			goRight(traverseArray, matrix);
			goDiagonalDown(traverseArray, matrix);
			goDown(traverseArray, matrix);
			goDiagonalUp(traverseArray, matrix);
		}

		return traverseArray.toArray(new Integer[] {});

	}

	private void goRight(List<Integer> traverseArray, int[][] matrix) {
		y++;
		if (y >= matrix.length) {
			y -- ;
			return;
		}
		traverseArray.add(matrix[x][y]);
	}

	private void goDiagonalDown(List<Integer> traverseArray, int[][] matrix) {

		x++;
		y--;
		while (true) {
			if (x >= matrix.length){
				x --;
				y ++;
				return;
			}
			if (y < 0) {
				x --;
				y ++;
				return;
			}
			if (traverseArray.contains(matrix[x][y])) {

				x --;
				y ++;
				return;
			}
			traverseArray.add(matrix[x][y]);
			x++;
			y--;
		}
	}

	private void goDown(List<Integer> traverseArray, int[][] matrix) {
		x++;
		if (x >= matrix.length) {

			x --;
			return;
		}
		traverseArray.add(matrix[x][y]);
	}

	private void goDiagonalUp(List<Integer> traverseArray, int[][] matrix) {
		x--;
		y++;

		while (true) {
			if (x < 0 ) {

				x ++;
				y --;
				return;
			}
			if (y >= matrix.length){
				x ++;
				y --;
				return;
			}
			if (traverseArray.contains(matrix[x][y])) {
				x ++;
				y --;
				return;

			}
			traverseArray.add(matrix[x][y]);
			x--;
			y++;
		}
	}

	public void print(int[][] data) {
		int m = data.length;
		int n = data[0].length;

		for (int i = 0; i < m; i++) {

			for (int j = 0; j < n; j++) {
				System.out.print(data[i][j] + " ");
			}
			System.out.println();
		}
	}
}

